package kmp;

public class leetCode43_multiply {
    public static void main(String[] args) {
        leetCode43_multiply a = new leetCode43_multiply();
        String multiply = a.multiply("123", "456");
        System.out.println(multiply);

    }


    public String multiply(String num1, String num2) {
        int n = num1.length();
        int m = num2.length();
        int[] a = new int[n];
        int[] b = new int[m];
        int[] c = new int[n + m];
        for (int i = n - 1; i >= 0; i--) {
            a[n - 1 - i] = num1.charAt(i) - '0';
        }
        for (int i = m - 1; i >= 0; i--) {
            b[m - 1- i] = num2.charAt(i) - '0';
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                c[i + j] += a[i] * b[j];
            }
        }
        int t = 0;
        for (int i = 0; i < c.length; i++) {
            t += c[i];
            c[i] = t%10;
            t = t/10;
        }
        int k = c.length - 1;
        while (k > 0 && c[k] == 0) k--;
        StringBuilder stringBuilder = new StringBuilder();
        while (k >= 0){
            stringBuilder.append(c[k]);
            k--;
        }
        return stringBuilder.toString();
    }

    public String multiply2(String num1, String num2) {
        if(num1 == null || num2 == null || num1.length() == 0 || num2.length() == 0) return null;
        if(num1.length() == 1 && num1.equals("0")) return "0";
        if(num2.length() == 1 && num2.equals("0")) return "0";
        char[] chars1 = num1.toCharArray();
        char[] chars2 = num2.toCharArray();
        int[] result = new int[chars1.length + chars2.length];

        for (int i = chars1.length - 1; i >= 0; i--) {
            int a = chars1[i] - '0';
            for (int j = chars2.length - 1; j >= 0; j--) {
                int b = chars2[j] - '0';
                int sum = result[i + j + 1] + a * b;
                result[i + j + 1] = sum % 10;
                result[i + j] += sum/10;
            }
        }

        StringBuilder res = new StringBuilder();
        for (int i = 0; i < result.length; i++) {
            if(i == 0 && result[i] == 0) continue;
            res.append(result[i]);
        }
        return res.toString();

    }

}
